package com.origin.niuke.tree;

import general_class.TreeNode;

import java.util.*;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/5/9 19:24
 * 输出二叉树的右视图
 * 算法：二叉树
 * 先根据前序和中序遍历构建一棵二叉树, 然后再用层次遍历找出每一层的最右边的数
 */
public class NC136 {

    int[] pre;
    int n;
    Map<Integer, Integer> map = new HashMap<>();
    public int[] solve (int[] xianxu, int[] zhongxu) {
        n = xianxu.length;
        if (n == 0) return new int[0];
        pre = xianxu;
        for (int i = 0; i < n; i++) map.put(zhongxu[i], i);
        TreeNode root = getRoot(0, n - 1, 0);
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        List<Integer> list = new ArrayList<>();
        while (!queue.isEmpty()) {
            int size = queue.size();
            Integer num = null;
            for (int i = 0; i < size; i++) {
                root = queue.poll();
                num = root.val;
                if (root.left != null) queue.offer(root.left);
                if (root.right != null) queue.offer(root.right);
            }
            list.add(num);
        }
        int[] ans = new int[list.size()];
        for (int i = 0; i < ans.length; i++) ans[i] = list.get(i);
        return ans;
    }
    TreeNode getRoot(int preBegin, int preEnd, int inBegin) {
        if (preBegin > preEnd) return null;
        TreeNode root = new TreeNode(pre[preBegin]);
        int idx = map.get(pre[preBegin]), leftSize = idx - inBegin;
        root.left = getRoot(preBegin + 1, preBegin + leftSize, inBegin);
        root.right = getRoot(preBegin + leftSize + 1, preEnd, idx + 1);
        return root;
    }

}
